public class java2024_5_7 {
    public static void main(String[] args) {
        int[] arr = {4, 1, 3, 2, 5, 6, 8, 7, 9, 10};
        int length = arr.length;
        QuickSort(arr, 0, length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    //三数取中
    public static int MidNumber(int[] arr, int left, int right) {
        int mid = (left + right) >> 1;
        if (arr[left] < arr[mid]) {
            if (arr[left] > arr[right])
                return left;
            else if (arr[right] > arr[mid])
                return mid;
            else
                return right;
        } else {
            if (arr[right] > arr[left])
                return left;
            else if (arr[right] < arr[mid]) {
                return mid;
            } else {
                return right;
            }
        }
    }


    //快速排序 - 前后指针法
    public static void QuickSort(int[] arr, int left, int right) {
        if (left >= right)
            return;
        int prev = left;
        int cur = prev + 1;

        int keyi = left;
        int key = arr[keyi];
        while (cur <= right) {
            if (arr[cur] < key) {
                prev++;
                arr[prev] = arr[cur];
            }
            cur++;
        }
        int temp = arr[prev];
        arr[prev] = arr[keyi];
        arr[keyi] = temp;
        keyi = prev;
        QuickSort(arr, left, keyi - 1);
        QuickSort(arr, keyi + 1, right);
    }

}
